Recently, it has become common practice to consider using FEC codes for protection of streaming media during transmission. When sent over a packet network, examples of which include the Internet and wireless networks such as those standardized by groups such as 3GPP, 3GPP2 and DVB, the source stream is placed into packets as it is generated or made available, and thus the packets are used to carry the source stream in the order it is generated or made available to receivers. In a typical application of FEC codes to these types of scenarios, the FEC code is used to add additional repair packets to the original source packets containing the source stream, and these repair packets have the property that when source packet loss occurs received repair packets can be used to recover the data contained in the lost source packets. In other examples, it is possible that partial packet loss occurs, i.e., receivers may lose parts of a packet while receiving other parts of that packet, and thus in these examples wholly or partially received repair packets can be used to recover wholly or partially lost source packets. In yet other examples, other types of corruption can occur to the sent data, e.g., values of bits may be flipped, and thus repair packets may be used to correct such corruption and provide as accurate as possible recovery of the source packets. In other examples, the source stream is not necessarily sent in discrete packets, but instead may be sent for example as a continuous bit-stream.
There are many examples of FEC codes that can be used to provide protection of a source stream. Reed-Solomon codes are well known codes for error and erasure correction in communication systems. For erasure correction over, for example, packet data networks, a well-known efficient implementation of Reed-Solomon codes is to use Cauchy or Vandermonde matrices as described in L. Rizzo, “Effective Erasure Codes for Reliable Computer Communication Protocols”, Computer Communication Review, 27(2):24-36 (April 1997) (hereinafter “Rizzo”) and Bloemer, ET AL., “An XOR-Based Erasure-Resilient Coding Scheme”, Technical Report TR-95-48, International Computer Science Institute, Berkeley, Calif. (1995) (hereinafter “XOR-Reed-Solomon”). Other examples of FEC codes include LDPC codes, chain reaction codes and multi-stage chain reaction codes, such as those described in U.S. Pat. No. 6,307,487 (hereinafter “Luby I”) and U.S. Published Patent App. No. 2003/0058958 (hereinafter “Shokrollahi I”), respectively, which are incorporated herein for all purposes.
Examples of the FEC decoding process for variants of Reed-Solomon codes are described in “Rizzo” and “XOR-Reed-Solomon”. In these examples, decoding is applied once sufficient source and repair data packets have been received. The decoding process may be computationally intensive and, depending on the CPU resources available, this may take considerable time to complete, relative to the length of time spanned by the media in the block. The receiver must take into account this length of time required for decoding when calculating the delay required between the start of reception of the media stream and play-out of the media. This delay due to decoding is perceived by the user as a delay between their request for a particular media stream and the start of playback. It is thus desirable to reduce this delay.
In many applications, packets are further sub-divided into symbols on which the FEC process is applied. A symbol can have any size, but often the size of a symbol is at most equal to the size of the packet. Hereinafter, we call the symbols comprising the encoding block the “source symbols,” and the symbols generated during the FEC process the “encoding symbols.” For some FEC codes, notably Reed-Solomon codes, the encoding and decoding time grows impractical as the number of encoding symbols per source block grows. Thus, in practice, there is often an upper bound, e.g., 255, on the total number of encoding symbols that can be generated per source block. Since symbols are placed into separate packet payloads, this places a practical upper bound on the maximum length on the encoding of a source block, e.g., if a packet payload is at most 1024 bytes, then an encoded source block can be at most 255 KB (kilobytes), and this is also, of course, an upper bound on the size of the source block itself.
Other concerns, such as being able to decode the source blocks fast enough to keep up with the source streaming rate, to minimize the decoding latency introduced by FEC decoding, and to only use a small fraction of the available CPU on the receiving device at any point in time during FEC decoding are issues.
Thus, it is desirable to have improved processes and apparatus.